﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"

//设置哨兵节点
DoubleList* Sentry()
{
	//开辟节点
	DoubleList* newnode = (DoubleList*)malloc(sizeof(DoubleList)); //开辟的是节点 不是节点的指针
	//判断空间有效性
	if (newnode == NULL)
	{
		printf("哨兵节点开辟失败\n");
		return NULL;
	}

	//初始化
	newnode->next = newnode;
	newnode->prev = newnode;

	return newnode;
}

//打印
void List_Print(DoubleList* pphead)
{
	//如果只有哨兵节点
	if (pphead->next == pphead)
	{
		printf("无元素可以打印\n");
		return;
	}
	//因为如果只有哨兵节点，pphead->next就越界了
	DoubleList* first = pphead->next;

	while (first != pphead)
	{
		printf("%d -> ", first->data);
		first = first->next;
	}
	printf("pphead\n");
}

//新增节点
DoubleList* Newnode(Plastic data)
{
	//开辟节点
	DoubleList* newnode = (DoubleList*)malloc(sizeof(DoubleList));
	//判断空间有效性
	if (newnode == NULL)
	{
		printf("节点开辟失败\n");
		return NULL;
	}

	//初始化
	newnode->next = newnode;
	newnode->prev = newnode;
	newnode->data = data;

	return newnode;
}

//尾插
void Tail_insert(DoubleList* pphead, Plastic data)
{
	//找尾
	DoubleList* tail = pphead->prev;
	//开辟节点
	DoubleList* newnode = Newnode(data);

	//连接
	pphead->prev = newnode;
	newnode->next = pphead;

	tail->next = newnode;
	newnode->prev = tail;
}

//尾删
void Tail_deletion(DoubleList* pphead)
{
	//如果只有头节点无法删除
	if (pphead->prev == pphead)
	{
		printf("无法删除\n");
		return;
	}

	//找尾
	DoubleList* tail = pphead->prev;
	//找倒数第二个节点
	DoubleList* cur = pphead->prev->prev;

	//更新关系，重新连接
	pphead->prev = cur;
	cur->next = pphead;

	free(tail);
	tail = NULL;
}

//头插
void Head_insert(DoubleList* pphead, int data)
{
	//标记头节点的下一个节点
	DoubleList* first = pphead->next;
	DoubleList* newnode = Newnode(5);

	//更新连接关系
	pphead->next = newnode;
	newnode->next = first;

	first->prev = newnode;
	newnode->prev = pphead;
}

//头删
void Head_deletion(DoubleList* pphead)
{
	//判断是否只有哨兵节点
	if (pphead->prev == pphead)
	{
		printf("无法删除\n");
		return;
	}

	//标记第一个节点
	DoubleList* first = pphead->next;
	//标记第二个节点
	DoubleList* second = first->next;

	//重新确立头节点和第二个节点的关系
	pphead->next = second;
	second->prev = first;

	//释放第一个节点
	free(first);
	first = NULL;
}

//在目标节点前面插入
void Before_target(DoubleList* pphead, int  data)
{
	//找目标节点
	DoubleList* cur = pphead->next;
	while (cur->data != data)
	{
		if (cur == pphead)
		{
			printf("没有找到\n");
			return;
		}
		cur = cur->next;
	}
	//标记cur前面的节点
	DoubleList* prev = cur->prev;
	DoubleList* newnode = Newnode(6);

	//将三者进行连接
	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = cur;
	cur->prev = newnode;
}

//在目标节点后面插入
void Behind_target(DoubleList* pphead, int data)
{
	//找目标节点
	DoubleList* cur = pphead->next;
	while (cur->data != data)
	{
		if (cur == pphead)
		{
			printf("没有找到\n");
			return;
		}
		cur = cur->next;
	}
	//标记cur后面的节点
	DoubleList* next = cur->next;
	DoubleList* newnode = Newnode(7);

	//将三者进行连接
	cur->next = newnode;
	newnode->prev = cur;

	newnode->next = next;
	next->prev = newnode;
}

//练习题1（反转字符串）
//while (next != NULL)
//{
//	pc->next = cur;
//
//	cur = pc ;
//	pc = next ;
//	next = next->next;
//}


//练习题2
//void Middle(DoubleList* pphead)
struct ListNode* middleNode(struct ListNode* head)
{
	//如果链表为空
	if (head == NULL)
	{
		return NULL;
	}

	//遍历链表、记录长度
	int count = 0;
	struct ListNode* cur = head;

	while (cur != NULL)
	{
		count++;
		cur = cur->next;
	}

	//计算中间节点
	count = count / 2 + 1;
	
	//再次找中间节点，并返回
	cur = head;
	while (cur != NULL)
	{
		count--;
		if (count == 0)
		{
			break;
		}
		cur = cur->next;
	}
	return cur;
}